package 排序算法.测试;

import 排序算法.冒泡排序.BubbleSort;
import 排序算法.基数排序.RadixSort;
import 排序算法.堆排序.HeapSort;
import 排序算法.希尔排序.ShellSort;
import 排序算法.归并排序.MergeSort;
import 排序算法.插入排序.InsertionSort;
import 排序算法.选择排序.SelectionSort;

import java.util.Random;

/*
测试排序之间的性能
Master定理
排序算法的时间消耗，除了跟本身的策略有关之外 还和数据的分布情况有关
常见的数据部分情况
1.完全随机
2.大致有序
3.大致平稳
            完全随机    大致有序    大致平稳
选择排序    580ms       230ms       300ms
冒泡排序    560ms       100ms       500ms
插入排序    100ms       10ms        80ms
希尔排序    30ms        15ms        20ms
归并排序    20ms        12ms        10ms
堆排序      550ms       300ms       500ms
基数排序    40ms        40ms        25ms
*/
public class TestSort {
    public static void main(String[] args) {
        int[] temp = getArr(1,10000);
        testSelectionSort(copy(temp));
        testBubbleSort(copy(temp));
        testInsertionSort(copy(temp));
        testSehllSort(copy(temp));
        testMergeSort(copy(temp));
        testHeapSort(copy(temp));
        testRadixSort(copy(temp));
    }

    private static void testRadixSort(int[] arr) {
        TimeUtil tu = new TimeUtil();
        tu.start();
        RadixSort.radixSort(arr);
        tu.stop();
        System.out.println("基数排序：" + tu.getPassedTime() + "ms");
    }

    private static void testHeapSort(int[] arr) {
        TimeUtil tu = new TimeUtil();
        tu.start();
        HeapSort.heapSort(arr);
        tu.stop();
        System.out.println("堆排序：" + tu.getPassedTime() + "ms");
    }

    private static void testMergeSort(int[] arr) {
        TimeUtil tu = new TimeUtil();
        tu.start();
        MergeSort.mergeSort(arr,0,arr.length - 1);
        tu.stop();
        System.out.println("归并排序：" + tu.getPassedTime() + "ms");
    }

    private static void testSehllSort(int[] arr) {
        TimeUtil tu = new TimeUtil();
        tu.start();
        ShellSort.shellSort(arr);
        tu.stop();
        System.out.println("希尔排序：" + tu.getPassedTime() + "ms");
    }

    private static void testInsertionSort(int[] arr) {
        TimeUtil tu = new TimeUtil();
        tu.start();
        InsertionSort.insertionSort(arr);
        tu.stop();
        System.out.println("插入排序：" + tu.getPassedTime() + "ms");
    }
    private static void testBubbleSort(int[] arr) {
        TimeUtil tu = new TimeUtil();
        tu.start();
        BubbleSort.bubbleSort(arr);
        tu.stop();
        System.out.println("冒泡排序：" + tu.getPassedTime() + "ms");
    }
    private static void testSelectionSort(int[] arr) {
        TimeUtil tu = new TimeUtil();
        tu.start();
        SelectionSort.selectionSort(arr);
        tu.stop();
        System.out.println("选择排序：" + tu.getPassedTime() + "ms");
    }

    private static int[] copy(int[] temp) {
        int[] copy = new int[temp.length];
        for (int i = 0; i < copy.length; i++) {
            copy[i] = temp[i];
        }
        return copy;
    }

    private static int[] getArr(int choice,int len) {
        Random random = new Random();
        int[] arr = new int[len];
        if (choice == 1) {
            for (int i = 0; i < arr.length; i++) {
                arr[i] = random.nextInt(100000);
            }
        } else if (choice == 2) {
            for (int i = 0; i < arr.length; i++) {
                arr[i] = i * 50 + random.nextInt(100);
            }
        } else {
            for (int i = 0; i < arr.length; i++) {
                arr[i] = 5000 + random.nextInt(500);
            }
        }
        return arr;
    }
}